package graph.traversal;

import java.util.*;

/**
 * @Classname : ReachableNodesInSubdividedGraph
 * @Description :
 * <a href="https://leetcode.cn/problems/reachable-nodes-in-subdivided-graph/">882. 细分图中的可到达节点</a>
 * 加权无向图：广度优先搜索 + 权重优先搜索
 * @Author : chentianyu
 * @Date 2023/2/7 23:49
 */


public class ReachableNodesInSubdividedGraph {
    public int reachableNodes(int[][] edges, int maxMoves, int n) {
        int nodeNum = 0;
        // 建立邻接矩阵
        List<List<int[]>> matrix = new ArrayList<>();
        for (int i = 0; i < n; i++) matrix.add(new ArrayList<>());
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            matrix.get(u).add(new int[]{v, w});
            matrix.get(v).add(new int[]{u, w});
        }
        // 优先队列实现权重优先遍历
        Queue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));  // 遍历到某节点走过的距离
        Map<Integer, Integer> dist = new HashMap<>();  // 记录遍历到某节点走过的距离（不包含当前节点）
        Map<Integer, Integer> used = new HashMap<>();  // 记录边上细分节点使用情况
        q.offer(new int[]{0, 0});
        dist.put(0, 0);

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int curNode = cur[0], curDist = cur[1];
            // 不同方向遍历到达同一个节点，只使用到达当前节点遍历距离最小的
            if (curDist > dist.getOrDefault(curNode, 0)) continue;
            nodeNum++;  // 遍历距离加上当前节点
            for (int[] next : matrix.get(curNode)) {
                int nextNode = next[0], nextWeight = next[1];
                int use = Math.min(nextWeight, maxMoves - curDist);
                used.put(curNode * n + nextNode, use);

                int nextDist = curDist + 1 + nextWeight;
                // nextDist < maxMoves + 1，说明还没遍历到最大距离
                // nextDist < dist.get(nextNode)，是为了保证不再逆向遍历已经遍历的节点
                if (nextDist < dist.getOrDefault(nextNode, maxMoves + 1)) {
                    q.offer(new int[]{nextNode, nextDist});
                    dist.put(nextNode, nextDist);
                }
            }
        }

        // 累加使用的细分节点
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            nodeNum += Math.min(w, used.getOrDefault(u * n + v, 0) + used.getOrDefault(v * n + u, 0));
        }
        return nodeNum;
    }
}
